//20. 有效的括号
// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。

#include <stdio.h>
#include <stdbool.h>


bool isValid(char* s) 
{
    //栈顶指针
    int top = -1;
    char stack[10000];

    for(int i = 0; s[i] != '\0'; i++)
    {
        char ch = s[i];
        if(ch == '(' || ch == '[' || ch == '{')
        {
            stack[++top] = ch;
        }
        else if(ch == ')' || ch == ']' || ch == '}')
        {
            //（在栈为空之后找到后括号）找到后括号但是前面没有前括号匹配
            if(top == -1)
                return false;
            char topchar = stack[top];
            if((ch == ')' && topchar == '(') || (ch == ']' && topchar == '[') || (ch == '}' && topchar == '{'))
                //匹配成功后出栈
                top--;
            else return false;
        }
    }
    //如果栈为空代表所有括号匹配成功
    return top == -1;
}

int main()
{
    char *s = "(){}";
    printf("%d\n",isValid(s));
    return 0;
}